package wh.环形链表2;

import java.util.*;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/1/12 16:14
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode(3,new ListNode(2,new ListNode(0,new ListNode(-4))));
        head.next.next.next.next = head.next;
        System.out.println(detectCycle(head).val);

    }

    //哈希 或者使用hashset
    public static ListNode detectCycle(ListNode head) {
     //   Set<ListNode> set = new HashSet<>();
        ListNode p = head;
        List<ListNode> list = new ArrayList<>();
        try {
            while (!list.contains(p)){
                list.add(p);
                p = p.next;
            }
        }catch (Exception e){
            return null;
        }

        return p;
    }

    public static ListNode detectCycle2(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }


}
